import java.util.HashMap;

/**
 * @ClassName LRUCache
 * @Date 2021/9/9 19:23
 * @Author 李明杰
 * @Description
 */
class Node {
    int key, value;
    Node prev, next;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

class DoubleList {
    Node tail, head;
    int size;

    public void printList(Node node) {
        while (node != null) {
            System.out.println(node.value);
            node = node.prev;
        }
    }
    //获取大小

    public int getSize() {
        return size;
    }

    //删除元素
    public void remove(Node node) {
        if (head == node && tail == node) {
            //        就一个节点时

            head = null;
            tail = null;

        } else if (tail == node) {
            //        删尾结点（此处写法不一致）
            node.prev.next = null;
            tail = tail.prev;
            node.prev = null;

        } else if (head == node) {
            //        删头结点

            head.next.prev = null;
            head = head.next;
            node.next = null;
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;

        }
        size--;
    }

    public Node removeLast() {
        Node node = this.tail;
        remove(node);
        return node;
    }

    //添加元素到头部
    public void addFirst(Node node) {
        if (head == null) {
            head = tail = node;
        } else {
            head.prev = node;
            node.next = head;
            head = node;

        }
        size++;
    }
}

public class LRUCache {
    private HashMap<Integer, Node> map;
    private DoubleList cache;
    private int capacity;

    public LRUCache(int capacity) {
        this.map = new HashMap<>();
        this.cache = new DoubleList();
        this.capacity = capacity;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        int val = map.get(key).value;
        //数据提到开头
        put(key, val);
        return val;
    }

    public void put(int key, int value) {
        Node x = new Node(key, value);
        if (map.containsKey(key)) {
            //更新链表和hashmap
            cache.remove(map.get(key));
            cache.addFirst(x);

            map.put(key, x);
        } else {
            if (capacity == cache.getSize()) {
                Node last = cache.removeLast();
                map.remove(last.key);

            }
            cache.addFirst(x);
            map.put(key, x);
        }
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(3);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        lruCache.put(3, 3);
        lruCache.put(4, 4);
        lruCache.put(5, 5);
        lruCache.put(2, 2);
        lruCache.cache.printList(lruCache.cache.tail);
    }

}
